package _2022.hot100._32_最长有效括号;

/**
 * @author： YHSimon
 * @date： 2022-04-06 14:35
 */
public class Solution {

    //427ms
    public int longestValidParentheses(String s) {
        int res=0;
        for(int i=0;i<s.length();i++){
            int balance=0;
            for(int j=i;j<s.length();j++){
                if(s.charAt(j)=='('){
                    balance++;
                }else{
                    balance--;
                }
                if(balance<0){
                    break;
                }else if (balance==0){
                    res=Math.max(res, j-i+1);
                }
            }
        }
        return res;
    }


    //动态规划
    public int longestValidParentheses2(String s) {
        if(s==null||s.length()<2) return 0;
        int res=0;
        int[] dp=new int[s.length()];
        
        for(int i=1;i<s.length();i++){
            if(s.charAt(i)==')'){
                int preLen=dp[i-1];
                int pre=i-1-preLen;
                if(pre>=0&&s.charAt(pre)=='('){
                    dp[i]=dp[i-1]+2;
                    
                    if(pre-1>=0){
                        dp[i]+=dp[pre-1];
                    }
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.longestValidParentheses(""));
    }
}
